package org.algorithm;


import java.awt.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

public class ReviewAgain {
}

/**
 * 普里姆算法：构造最小生成数
 * 1.遍历每个节点，找到距离当前节点最近的一个未加入最小生成树的节点
 * 2.并将该节点设置为已加入最小生成树
 */
class PrimReview {
    private char[] vertex;
    private int[] isVisited;
    private int[][] matrix;

    public PrimReview(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
        this.isVisited = new int[vertex.length];
    }

    public static void main(String[] args) {
        char[] data = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邻接矩阵的关系使用二维数组表示,10000这个大数，表示两个点不联通
        int[][] weight = new int[][]{
                {10000, 5, 7, 10000, 10000, 10000, 2},
                {5, 10000, 10000, 9, 10000, 10000, 3},
                {7, 10000, 10000, 10000, 8, 10000, 10000},
                {10000, 9, 10000, 10000, 10000, 4, 10000},
                {10000, 10000, 8, 10000, 10000, 5, 4},
                {10000, 10000, 10000, 4, 5, 10000, 6},
                {2, 3, 10000, 10000, 4, 6, 10000},};

        //创建MGraph对象
        //创建一个MinTree对象
        //输出
        PrimReview prim = new PrimReview(data, weight);
        prim.algorithom(0);
    }

    public void algorithom(int index) {

        isVisited[index] = 1;
        int h1 = 0, h2 = 0;
        for (int k = 0; k < vertex.length - 1; k++) {
            int min = 10000;

            for (int i = 0; i < matrix.length; i++) {

                for (int j = 0; j < matrix[i].length; j++) {

                    if (isVisited[i] == 1 && isVisited[j] == 0 && matrix[i][j] < min) {
                        min = matrix[i][j];
                        h1 = i;
                        h2 = j;
                    }

                }

            }
            isVisited[h2] = 1;
            System.out.println("从" + vertex[h1] + "到" + vertex[h2] + " = " + matrix[h1][h2]);
        }
    }
}

/**
 * 迪杰斯特拉算法: 广度优先找到最近的一个节点,然后使用该节点的距离链接其他节点,使开始节点距离各个节点距离最近
 * 1.找到距离当前节点距离最近的节点后遍历其他未使用过的节点,
 * 2.使当前节点距离开始节点距离+ 当前节点和遍历的节点距离小于 遍历节点与开始节点距离 那么就更新距离
 */
class DijkstraReview {
    private int[] preVertex;
    private int[] dis;
    private char[] vertex;
    private int[][] matrix;
    private boolean[] isVisited;
    private static int N = 66535;


    public DijkstraReview(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;
        this.isVisited = new boolean[vertex.length];
        this.preVertex = new int[vertex.length];
        dis = new int[vertex.length];
        Arrays.fill(dis, N);
    }

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];

        matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, N, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, N, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, N, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, N};

        DijkstraReview dijkstra = new DijkstraReview(vertex, matrix);
        dijkstra.show();
        dijkstra.algorithm(2);
        dijkstra.shwoDijkstra();
    }


    public void show() {
        for (int i = 0; i < vertex.length; i++) {
            for (int j = 0; j < vertex.length; j++) {
                System.out.printf("%-6d", matrix[i][j]);
            }
            System.out.println();
        }
    }

    public void shwoDijkstra() {

        System.out.println(Arrays.toString(isVisited));
        System.out.println(Arrays.toString(preVertex));

        for (int i = 0; i < dis.length; i++) {

            System.out.println(vertex[i] + " = " + dis[i]);
        }
    }

    public void algorithm(int index) {
        dis[index] = 0;
        isVisited[index] = true;
        update(index);
        for (int i = 0; i < vertex.length - 1; i++) {
            int next = next();
            update(next);
        }

    }


    /**
     * 功能: 使用index当前驱节点时,距离起始节点的距离是否是最近,如果是就更新距离
     * 1.通过index可以使起始节点和i这个节点相连
     * 2.通过index作为前驱节点时,距离起始节点的距离是否是更近,如果是就更新距离
     *
     * @param index
     */
    public void update(int index) {

        int len;
        for (int i = 0; i < matrix[index].length; i++) {
            len = dis[index] + matrix[index][i];

            if (len < dis[i]) {
                dis[i] = len;
                preVertex[i] = index;
            }
        }
    }


    /**
     * 功能: 返回当前节点最近的节点
     *
     * @return
     */
    public int next() {
        int min = 65535;
        int index = 0;
        for (int i = 0; i < dis.length; i++) {
            if (!isVisited[i] && dis[i] < min) {
                min = dis[i];
                index = i;
            }
        }

        isVisited[index] = true;
        return index;
    }

}

/**
 * 弗洛伊德算法: 使用三个for循环求每个节点距离其它节点的最短距离
 * 1.经过中间节点是否是最短距离
 * 2.如果开始和结束节点没有直接相连,那么通过中间节点链接两点
 */
class FloydReview {
    private int[][] preVertex;
    private int[][] matrix;
    private char[] vertex;

    public FloydReview(char[] vertex, int[][] matrix) {
        this.vertex = vertex;
        this.matrix = matrix;

        this.preVertex = new int[vertex.length][vertex.length];

        for (int i = 0; i < preVertex.length; i++) {
            Arrays.fill(preVertex[i], i);
        }
    }

    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //创建邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;
        matrix[0] = new int[]{0, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, 0, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, 0, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, 0, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, 0, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, 0, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, 0};

        FloydReview floyd = new FloydReview(vertex, matrix);
        floyd.show();
        floyd.algorithm();
        floyd.show();
    }


    public void show() {
        for (int i = 0; i < preVertex.length; i++) {
            for (int j = 0; j < preVertex[i].length; j++) {


                System.out.print(vertex[preVertex[i][j]] + "\t");
            }
            System.out.println();
            for (int j = 0; j < preVertex[i].length; j++) {
                System.out.print("(" + vertex[i] + "到" + vertex[j] + "的最短路径是" + matrix[i][j] + ") ");

            }
            System.out.println();
        }
    }

    public void algorithm() {
        int len;
        //TODO: 查找所有经过该节点的最近路径
        for (int k = 0; k < vertex.length; k++) {

            //TODO: 开始节点
            for (int i = 0; i < vertex.length; i++) {
                //TODO: 结束节点
                for (int j = 0; j < vertex.length; j++) {

                    len = matrix[i][k] + matrix[k][j];

                    if (len < matrix[i][j]) {
                        matrix[i][j] = len;
                        preVertex[i][j] = preVertex[k][j];
                    }

                }
            }
        }
    }
}

/**
 * 骑士周游算法：主要使用递归和回溯完成
 * 1.递归去找可以走的路
 * 2.回溯是将走过的路进行恢复初始状态（未走状态）
 */
class ChessBaord {
    //TODO: 节点
    private boolean[] isVisited;
    private int[][] preVertex;
    private int X;
    private int Y;
    private boolean finished = false;
    private int step;

    public ChessBaord(int column, int row) {
        X = column;
        Y = row;
        this.isVisited = new boolean[column * row];
        this.preVertex = new int[row][column];

    }


    public static void main(String[] args) {
        ChessBaord chessBaord = new ChessBaord(8, 8);
        long start = System.currentTimeMillis();
        chessBaord.chessBoard(0, 0, 1);
        long end = System.currentTimeMillis();
        System.out.println("共耗时: " + (end - start) + " 毫秒");

        for (int[] preVertex : chessBaord.preVertex) {
            for (int vertex : preVertex) {
                System.out.print(vertex + "\t");
            }
            System.out.println();
        }

    }

    public void chessBoard(int column, int row, int step) {

        isVisited[row * X + column] = true;
        preVertex[row][column] = step;

        ArrayList<Point> ps = next(new Point(column, row));
        ps.sort(new Comparator<Point>() {
            @Override
            public int compare(Point o1, Point o2) {
                return next(o1).size() - next(o2).size();
            }
        });
        while (!ps.isEmpty()) {
            Point point = ps.remove(0);
            if (!isVisited[point.y * X + point.x]) {
                chessBoard(point.x, point.y, step + 1);
            }
        }

        if (step < X * Y && finished == false) {
            isVisited[row * X + column] = false;
            preVertex[row][column] = 0;
        } else {
            finished = true;
        }

    }

    /**
     * 功能：找到下一步可走的所有路径
     *
     * @param curPoint 棋当前位置
     * @return 返回可走棋点的集合
     */
    public ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> ps = new ArrayList<>();
        Point p1 = new Point();
        /**
         * 按照当前传入的point为中间位置，分别计算马可以走的所有位置
         */

        //跳到5这个位置的时候
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //跳到6这个位置的时候
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //跳到7这个位置的时候
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y - 2) >= 0) {
            ps.add(new Point(p1));
        }
        //跳到0这个位置的时候
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y - 1) >= 0) {
            ps.add(new Point(p1));
        }
        //跳到1这个位置的时候
        if ((p1.x = curPoint.x + 2) < X && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        //跳到2这个位置的时候
        if ((p1.x = curPoint.x + 1) < X && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //跳到3这个位置的时候
        if ((p1.x = curPoint.x - 1) >= 0 && (p1.y = curPoint.y + 2) < Y) {
            ps.add(new Point(p1));
        }
        //跳到4这个位置的时候
        if ((p1.x = curPoint.x - 2) >= 0 && (p1.y = curPoint.y + 1) < Y) {
            ps.add(new Point(p1));
        }
        return ps;
    }

}